import collections
# class StreamChecker(object):

#     def __init__(self, words):
#         """
#         :type words: List[str]
#         """
#         self.base = 10 ** 9 + 7
#         self.max_n = 0
#         self.d = collections.defaultdict(set)
#         for word in words:
#             self.max_n = max(self.max_n, len(word))
#             ans = 0
#             for c in word:
#                 ans = (ans * 27 + ord(c) - ord('a')) % self.base
#             self.d[ans].add(word)
#         self.st = []
#         self.hash = [0] * self.max_n
#     def query(self, letter):
#         """
#         :type letter: str
#         :rtype: bool
#         """
#         self.st.append(letter)
#         o = ord(letter) - ord('a')
#         r_flag = False
#         for i in range(self.max_n - 2, -1, -1):
#             now_val = (self.hash[i] * 27 + o) % self.base
#             if now_val in self.d:
#                 l = i + 2
#                 if len(self.st) >= l and ''.join(self.st[-l:]) in self.d[now_val]:
#                     r_flag = True
#             self.hash[i + 1] = now_val
#         self.hash[0] = o
#         if o in self.d:
#             if letter in self.d[o]:
#                 r_flag = True
#         return r_flag
import collections
class Node:
    def __init__(self):
        self.children = [None] * 26
        self.fail = None
class StreamChecker(object):
    def __init__(self, words):
        self.tree = Node()
        for word in words:
            node = self.tree
            for c in word:
                index = ord(c) - ord('a')
                if node.children[index]:
                    node = node.children[index]
                else:
                    new_node = Node()
                    node.children[index] = new_node
                    node = new_node
        node = self.tree
        st = collections.deque()
        for i in range(26):
            if node.children[i]:
                node.children[i].fail = node
                st.append(node.children[i])
            else:
                node.children[i] = node ## 如果为空直接指向根节点
        while st:
            node = st.popleft()
            for i in range(26):
                if node.children[i]:
                    node.children[i].fail = node.fail.children[i]
                    st.append(node.children[i])
                else:
                    node.children[i] = node.fail.children[i] ##如果为空指向上一个匹配上的节点或根节点
        self.temp = self.tree

    def query(self, letter: str) -> bool:
        index = ord(letter) - ord('a')
        self.temp = self.temp.children[index]
        return self.temp.is_end     

data = StreamChecker(["cd","f","kl"])
print(data.query('a'))





                    

            

            


            
        

        
        